#include<iostream>
#include<cstring>

using namespace std;

int n,m;
int dp[10001][101];
int value[101];
int time[101];
int main()
{
	cin >> n >> m ;
	for (int i=1;i<=m;i++)
		cin >> time[i] >> value[i];
	for (int i=0;i<=m;i++)
		dp[0][i] = 0;
	for (int i=0;i<=n;i++)
		dp[i][0] = 0;
	
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (i<time[j])
			{
				dp[i][j] = dp[i][j-1];
			}
			else {
				dp[i][j] = max(dp[i][j-1],dp[i-time[j]][j-1]+value[j]);
			}
		}
	}
	/**/
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			printf("%d\t",dp[i][j]);
		}
		printf("\n");
	}
	
	printf("%d\n",dp[n][m]);
	//diguis();
	return 0;	
} 
